package com.kwt.learn.algorithm;


/**
 * 问题描述
 * 汉明距离问题
 * 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
 * 给出两个整数 x 和 y，计算它们之间的汉明距离。
 * <p>
 * 示例：
 * 输入: x = 1, y = 4
 * 输出: 2
 * 解释:
 * 1   (0 0 0 1)
 * 4   (0 1 0 0)
 * ↑   ↑
 * 上面的箭头指出了对应二进制位不同的位置。
 */


public class Solution03 {
    public static void main(String[] args) {
        System.out.println(hammingDistance1(25, 3789));
    }

    /**
     * 解题思路
     * 既然是要求二进制不同的位的个数，则应该想到应用位运算
     * 异或运算：两个二进制数，从高位开始比较，相同的结果为0，不同的结果为1
     * 异或运算之后再数一下有多少个1
     *
     * @param x
     * @param y
     * @return
     */
    public static int hammingDistance(int x, int y) {
        //异或运算
        int i = x ^ y;
        //将十进制转换为二进制
        String s = Integer.toBinaryString(i);
        String replace = s.replace("1", "");
        return s.length() - replace.length();

    }


    public static int hammingDistance1(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

}
